Выпуклая оптимизация: Основы аппроксимации норм

Представьте, что вы портной, пытающийся подогнать стандартный костюм (диапазон матрицы $A$) клиенту с уникальными пропорциями (вектор $b$). Независимо от того, как вы корректируете рукав или пояс (коэффициенты $x$), костюм никогда не будет идеально прилегать. Вы ищете «наилучшее» компромиссное решение — аппроксимация норм которое минимизирует напряжение или «остаток» в каждом шве.

Математическая основа

Основная цель — найти вектор $x \in \mathbb{R}^n$, такой что линейная комбинация $Ax = x_1a_1 + \dots + x_na_n$ наилучшим образом аппроксимирует $b$. Это часто называют регрессией $b$ на регрессоры (столбцы матрицы $A$).

Мы сосредоточены на векторе остатков $r = Ax - b$. На практике мы предполагаем переопределённую систему где $m > n$. Почему? Потому что при $m = n$ и невырожденной матрице $A$ оптимальная точка просто $A^{-1}b$, что даёт нулевую ошибку — тривиальный случай для оптимизации.

🎯 Ключевой принцип

Задача аппроксимации норм (6.1) является выпуклой задачей и гарантированно является разрешимой. Всегда существует хотя бы одно оптимальное решение $\hat{x}$, которое минимизирует расстояние между целью и достижимым подпространством.

Канонические вариации

В зависимости от «характера» ошибки, которую мы хотим наказывать, выбираем разные нормы:

1. Метод наименьших квадратов ($\ell_2$ норма)

Наиболее распространённый подход. Он минимизирует сумму квадратов остатков: $\|Ax - b\|_2^2$. Чувствителен к большим выбросам, но предоставляет аналитическое решение через нормальные уравнения.

2. Чебышёва / Минимакс ($\ell_\infty$ норма)

Минимизирует максимум абсолютного остатка $\max_i |r_i|$. Используется, когда каждое измерение должно оставаться в строгих пределах допуска. Может быть решено с помощью следующей линейной программы (ЛП):

минимизировать $t$
при условии $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

3. Сумма абсолютных остатков ($\ell_1$ норма)

Минимизирует $\sum |r_i|$. Этот подход устойчив к выбросам, так как не возводит ошибки в квадрат. Также может быть решён с помощью ЛП:

минимизировать $\mathbf{1}^T t$
при условии $-t \preceq Ax - b \preceq t$

Контекст оценки

Во многих инженерных областях мы предполагаем, что истинное состояние $x$ маскируется шумом: $y = Ax + v$. Наша цель — найти оценку $\hat{x} = \text{argmin}_z \|Az - y\|$. Выбирая норму, мы фактически делаем предположение о статистическом распределении шума $v$.

\text{Минимизировать } \|u - b\| \text{ при условии } u \in \mathcal{A} \quad (\text{где } \mathcal{A} = \text{Range}(A))

ВОПРОС 1

В контексте аппроксимации норм почему мы обычно предполагаем, что $m > n$?

Потому что если $m = n$, то решение тривиально: $x = A^{-1}b$ с нулевым остатком.

Чтобы обеспечить, что задача остаётся невыпуклой.

Потому что норма $\ell_1$ требует больше переменных, чем ограничений, для решения.

Чтобы гарантировать, что матрица $A$ всегда вырождена.

ВОПРОС 2

Какая формулировка линейного программирования (ЛП) правильно представляет задачу аппроксимации Чебышёва (минимакс)?

минимизировать $t$ при условии $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$

минимизировать $\mathbf{1}^T t$ при условии $-t \preceq Ax - b \preceq t$

минимизировать $\|Ax - b\|_2$ при условии $x \succeq 0$

минимизировать $t$ при условии $Ax - b = t$

ВОПРОС 3

Вы калибруете датчик и хотите гарантировать, что ни одно измерение никогда не отклоняется от модели более чем на фиксированную величину. Какую норму следует использовать?

L∞ (Чебышёв)

L₁ (сумма абсолютных остатков)

L₂ (метод наименьших квадратов)

Норма Фробениуса

ВОПРОС 4

Что верно относительно разрешимости задачи аппроксимации норм (6.1)?

Она всегда разрешима и выпукла.

Она разрешима только если матрица $A$ симметрична.

Она не выпукла, если используется норма $\ell_1$.

У системы нет решения, если она переопределена.

ВОПРОС 5

В выражении $y = Ax + v$, если $v$ представляет собой лапласовский шум (имеющий «толстые» хвосты по сравнению с гауссовским шумом), какая норма аппроксимации статистически более устойчива?

L₁ (сумма абсолютных остатков)

L₂ (метод наименьших квадратов)

L∞ (Чебышёв)

Псевдо-норма $L_0$

Задание: Проектирование калибровки датчика

Практическое моделирование

Робототехник калибрует трёхосевой акселерометр, используя 100 выборочных измерений ($m=100$), чтобы определить три физических коэффициента калибровки ($n=3$). Пусть $A$ — матрица размером $100 \times 3$ наблюдений, а $b$ — целевые значения отсчётов.

Вопрос 1

Если инженер подозревает, что 5% измерений являются «сбоями» (экстремальными выбросами, вызванными электрическими помехами), какую норму следует выбрать, и какова её форма ограничений ЛП?

Решение: Используйте норму $L_1$ (сумму абсолютных остатков). Её форма ЛП:
Минимизировать $\mathbf{1}^T t$
При условии: $-t \preceq Ax - b \preceq t$.
Это предпочтительнее, потому что норма $L_1$ не возводит остатки в квадрат, делая её менее чувствительной к большим ошибкам «сбоев», чем $L_2$.

Вопрос 2

Что происходит с оптимальным решением, если перейти от $L_2$ к $L_\infty$?

Решение: Решение $L_2$ (наименьшие квадраты) пытается уменьшить «среднюю» квадратичную ошибку по всем 100 датчикам. Решение $L_\infty$ (Чебышёв) исключительно фокусируется на уменьшении единственной наибольшей ошибки. Это обычно приводит к более равномерным ошибкам по всем датчикам, но к более высокой общей сумме квадратов ошибок.